package com.leetcode.partition4;

import java.util.Arrays;

/**
 * @author `RKC`
 * @date 2021/9/27 18:01
 */
public class LC304二维区域和检索_矩阵不可变 {

    public static void main(String[] args) {
        int[][] matrix = {
                {3, 0, 1, 4, 2},
                {5, 6, 3, 2, 1},
                {1, 2, 0, 1, 5},
                {4, 1, 0, 1, 7},
                {1, 0, 3, 0, 5}
        };
        NumMatrix numMatrix = new NumMatrix(matrix);
        System.out.println(numMatrix.sumRegion(2, 1, 4, 3));
        System.out.println(numMatrix.sumRegion(1, 1, 2, 2));
    }

    private static class NumMatrix {

        private int[][] matrix;
        private int[][] dp;

        public NumMatrix(int[][] matrix) {
            this.matrix = matrix;
            dp = new int[matrix.length + 1][matrix[0].length + 1];
            //对dp数组进行初始化，dp[i][j]存的是以matrix[0][0]为顶点，matrix[i-1][j-1]为终点的矩阵前缀和
            for (int i = 1; i < dp.length; i++) {
                for (int j = 1; j < dp[0].length; j++) {
                    dp[i][j] = dp[i - 1][j] + dp[i][j - 1] + matrix[i - 1][j - 1] - dp[i - 1][j - 1];
                }
            }
            Arrays.stream(dp).forEach(val -> System.out.println(Arrays.toString(val)));
        }

        public int sumRegion(int row1, int col1, int row2, int col2) {
            int answer = dp[row2 + 1][col2 + 1];
            answer -= dp[row1][col2 + 1] + dp[row2 + 1][col1];
            answer += dp[row1][col1];
            return answer;
        }
    }
}
